1. Field of the Invention
The invention relates generally to processing data, and more particularly, to the processing of non-contiguous data elements in a unit of data.
2. Description of Related Art
Routers receive data on a physical media, such as optical fiber, analyze the data to determine its destination, and output the data on a physical media in accordance with the destination. Routers were initially designed using a general purpose processor executing large software programs. As line rates and traffic volume increased, however, general purpose processors could not scale to meet these new demands. For example, as functionality was added to the software, such as accounting and policing functionality, these routers suffered performance degradation. In some instances, the routers failed to handle traffic at a line rate when the new functionality was implemented.
To meet the new demands, purpose-built routers have been designed with components optimized for routing. These routers not only handle higher line rates and higher network traffic volume, they also add functionality without compromising line rate performance.
A purpose-built router may include a number of input and output ports from which it transmits and receives information packets. A packet received at one port is typically directed to its appropriate output port based on an examination and processing of the packet's header information, which includes an indication of the packet's destination. A high-performance router must accordingly examine and process the information packets at a high speed.
In a purpose-built router, it may be desirable to process non-contiguous data in, for example, the header of a packet. FIG. 1 is a block diagram illustrating exemplary processing of a packet of data 110 by a processor 120 to generate a modified packet 130. Packet 110 may include data elements A, B, and C respectively located at non-contiguous locations 1, 2, and 3 in the packet. Data elements A–C conceptually represent elements of interest in packet 110, and need not be located in the header of packet 110. Further, data elements 110 may be fewer or greater in number, and may be partly contiguous (e.g., A and B may be adjacent, but C may be spaced from A and B).
Processor 120 may perform processing (e.g., route look-up) based on some of data elements A–C, and may replace some of the data elements at locations 1–3 with modified data elements (e.g., D and E, possibly reflecting a new route) to generate the modified packet 130. In FIG. 1, processor 120 may be configured to: read data element A from location 1 and read data element B from location 2 in packet 110; perform computations based on data elements A and B; and write data element D to location 1 and write data element E to location 3 in the packet. Such processing conceptually illustrates three cases: location 1 may be read and written; location 2 may be read but not written; and location 3 may be written but not read.
The arrangement shown in FIG. 1 may suffer from poor performance, however, due to the phenomenon of “spatial locality.” Processor 120 generally reads and/or writes data from non-contiguous locations (e.g., locations 1–3) more slowly than, for example, a contiguous block of data. Also, packet 110 may be stored in a memory (not shown) during processing by processor 120. The time needed to access the memory may also delay processing of packet 110.
Thus, it is desirable to improve the speed of processing non-contiguous data elements in a unit of data such as a packet.